package leetcode_acm.leetcode_1;

import org.junit.Test;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月09日 22:57
 */
public class BinaryTreePaths {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    public static final String SEP = "->";
    private static LinkedList<String> list = new LinkedList<>();
    public static List<String> binaryTreePaths(TreeNode root) {
        if(root == null) {
            return Collections.emptyList();
        }
        backtrack(root,new StringBuilder().append(root.val));
        return list;
    }

    private static void backtrack(TreeNode root, StringBuilder sb){
        //递归边界
        if(root.left == null && root.right == null){
            //在这里进行一次结算
            list.addLast(sb.toString());
        }
        //做出选择
        if(root.left!=null){
            int length = sb.length();
            String ele = SEP+root.left.val;
            int end = length+ele.length();
            sb.append(ele);
            //递归回溯
            backtrack(root.left,sb);
            //撤销选择
            sb.delete(length,end);
        }
        if(root.right!=null){
            int length = sb.length();
            String ele = SEP+root.right.val;
            int end = length+ele.length();
            sb.append(ele);
            //递归回溯
            backtrack(root.right,sb);
            //撤销选择
            sb.delete(length,end);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        //buildTree
        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for(int i = 1;i<n;){
            int left = nums[i++];
            TreeNode head = q.poll();
            if(left != -1){
                head.left = new TreeNode(left);
                q.offer(head.left);
            }
            int right = nums[i++];
            if(right != -1){
                head.right = new TreeNode(right);
                q.offer(head.right);
            }
        }
        binaryTreePaths(root);
        System.out.println(Arrays.toString(list.toArray()));
    }


}
